class Solution {
public:
    /**
     * retrun the longest increasing subsequence
     * @param arr int整型vector the array
     * @return int整型vector
     */
    /*
    d[i]表示长度为i的最长的上升子序列的末尾数字
    p[i]表示arr[i]在数组d中位置
    如果arr[i]>b[len];将arr[i]直接插入到b数组的后面，len++;
    如果arr[i]<=b[len]
    用arr[i]替换掉b数组中第一个大于或者等于arr[i]的元素
    */
     vector<int> LIS(vector<int>& arr) {
        int n = arr.size();
        vector<int> d(n + 1, -1), p(n);
        int len = 1;//初始化长度为1，元素为序列第一个数字
        d[len] = arr[0];
        p[0] = 1;//表示下标为arr[0]在d数组中的位置
        for(int i = 1; i < n; ++i) {
            if(arr[i] > d[len]) {
                //此时将该数字添加到末尾
                d[++len] = arr[i];
                p[i] = len;
            } else {
                //二分查找恰好合适的位置
                int left = 1, right = len, pos = 0;
                while(left <= right) {
                    int mid = (left + right) / 2;
                    if(d[mid] < arr[i]) {
                        pos = mid;
                        left = mid + 1;
                    } else {
                        right = mid - 1;
                    }
                }
                //对该位置数字进行更新
                d[pos + 1] = arr[i];
                p[i] = pos + 1;
            }
        }
        vector<int> ans(len);
        //逆向遍历p数组查找对应序列值
        for(int i = n - 1; i >= 0; --i) {
            if(p[i] == len) {
                ans[--len] = arr[i];
            }
        }
        return ans;
    }
    
};